// Sort.cpp

#define MAXSIZE 20
typedef int KeyType;

typedef struct
{
    KeyType key ;
    InfoType otherinfo;
}RedType;

typedef struct
{
    RedType r[MAXSIZE+1];
    int length;
}SqList;

void InsertSort(SqList &L)
{
    // 对顺序表L作直接插入排序
    for(int i = 2; i <= L.length; ++i)
    {
        if(L.r[i].key < L.r[i-1].key)
        {
            L.r[0] = L.r[i];
            L.r[i] = L.r[i-1];
            for(int j = i-2; L.r[0].key < L.r[j].key; --j)
            {
                L.r[j+1] = L.r[j];
            }
            L.r[j+1] = L.r[0];
        }
    }
}

void BInsertSort(SqList &L)
{
    // 对顺序表L作折半插入排序
    for(int i = 2; i <= L.length; ++i)
    {
        L.r[0] = L.r[i];
        int low = 1;
        int high = i - 1;
        while(low <= high)
        {
            int m = (low + high) / 2;
            if(L.r[0].key < L.r[m].key)
            {
                high = m - 1;
            }
            else
            {
                low = m + 1;
            }
        }

        for(int j = i-1; j >= high+1; --j)
        {
            L.r[j+1] = L.r[j];
        }

        L.r[high+1] = L.r[0];
    }
}

void ShellInsert(SqList &L, int dk)
{
    // 对顺序表L作一趟希尔插入排序
    // 前后记录位置的增量是dk，而不是1；
    // r[0]只是暂存单元，不是哨兵，当j<=0时，插入位置已找到。
    for(int i = dk+1; i <= L.length; ++i)
    {
        if(L.r[i].key < L.r[i-dk].key)
        {
            L.r[0] = L.r[i];
            for(int j = i-dk; j > 0 && L.r[0].key < L.r[j].key; j -= dk)
            {
                L.r[j+dk] = L.r[j];
            }
            L.r[j+dk] = L.r[0];
        }
    }
}

void ShellSort(SqList &L, int dlta[], int t)
{
    for(int k = 0; k < t; ++k)
    {
        ShellInsert(L, dlta[k]);
    }
}

KeyType pivotKey;

int Partition(SqList &L, int low, int high)
{
    // 交换顺序表L中字表L.r[low..high]的记录，使枢轴记录到位，并返回其所在位置，此时在它之前（后）的记录均不大（小）于它。
    pivotKey = L.r[low].key;

    while(low < high)
    {
        while(low < high && L.r[high].key >= pivotKey)
        {
            --high;
        }
        swap(L.r[low], L.r[high]);

        while(low < high && L.r[low].key <= pivotKey)
        {
            ++low;
        }
        swap(L.r[low], L.r[high]);
    }

    return low;
}

void QuickSort(SqList &L, int low, int high)
{
    // 快速排序
    if(low < high)
    {
        KeyType pivotLoc = Partition(L, low, high);
        QuickSort(L, low, pivotLoc-1);
        QuickSort(L, pivotLoc+1, high);
    }
}

QuickSort(L, 1, L.length);

void heapify(int[] array, int curRootNode, int size)
{
    if(curRootNode < size)
    {
        // 左子树和右子树的位置
        int left = curRootNode * 2 + 1;
        int right = curRootNode * 2 + 2;

        // 把当前父节点位置当做最大的
        int max = curRootNode;

        if(left < size)
        {
            // 如果比当前根元素要大，记录其位置。
            if(array[max] < array[left])
            {
                max = left;
            }
        }

        if(right < size)
        {
            // 如果比当前根元素要大，记录其位置。
            if(array[max] < array[right])
            {
                max = right;
            }
        }

        // 如果最大的不是根元素位置，则交换。
        if(max != curRootNode)
        {
            int temp = array[max];
            array[max] = array[curRootNode];
            array[curRootNode] = temp;

            // 继续比较，直到完成一次建堆。
            heapify(array, max, size);
        }
    }
}

// 完成一次建堆，最大值在堆的顶部（根节点）
void maxHeapify(int[] array, int size)
{
    // 从数组的尾部开始，直到第一个元素（角标为0）。
    for(int i = size - 1; i >= 0; --i)
    {
        heapify(arrays, i, size);
    }
}

for(int i = 0; i < array.length, ++i)
{
    // 每次建堆就可以排除一个元素了
    maxHeapify(array, array.length - i);

    // 交换
    int temp = array[0];
    array[0] = array[(array.length-1) - i];
    array[(array.length01) - i] = temp;
}

//////////////////////归并排序/////////////////////
void Merge(RcdType SR[], RcdType &TR[], int i, int m, int n)
{
    // 将有序的SR[i..m]和SR[m+1..n]归并为有序的TR[i..n]
    for(int j = m+1, int k = i; i <= m && j <= n; ++k)
    {
        if(SR[i].key < SR[j].key)
        {
            TR[k] = SR[i++];
        }
        else
        {
            TR[k] = SR[j++];
        }
    }

    if (j <= m)
    {
        TR[k..n] = SR[i..m];
    }

    if (j <= n)
    {
        TR[k..n] = SR[j..n]
    }
}

void MSort(RcdType SR[], RcdType &TR1[], int s, int t)
{
    // 将SR[s..t]归并排序为TR1[s..t]
    if(s == t)
    {
        TR1[s] = SR[s];
    }
    else
    {
        int m = (s + t) / 2;            // 将SR[s..t]平分为SR[s..m]和SR[m+1..t]
        MSort(SR, TR2, s, m);           // 递归将SR[s..m]归并为有序的TR2[s..m]
        MSort(SR, TR2, m+1, t);         // 递归将SR[m+1..t]归并为有序的TR2[m+1..t]
        MSort(TR2, TR1, s, m, t);       // 将TR2[s..m]和TR2[m+1..t]归并到TR1[s..t]
    }
}

void MergeSort(SqList &L)
{
    MSort(L.r, L.r, 1, L.length);
}

//////////////////////基数排序/////////////////////
// 辅助函数，求数据的最大位数。
int maxbit(int data[], int n)
{
    int maxData = data[0];
    // 先求出最大数，再求其位数。
    for(int i = 1; i < n; ++i)
    {
        if (maxData < data[i])
        {
            maxData = data[i];
        }
    }

    int d = 1;
    int p = 10;

    while (maxData >= p)
    {
        maxData /= 10;
        ++d;
    }
    
    return d;
}

void radixSort(int data[], int n)
{
    int d = maxbit(data, n);
    int *temp = new int[n];
    int *count = new int[10];   // 计数器
    int i,j,k;
    int radix = 1;

    for (i = 1; i <= d; i++)       // 进行d次排序
    {
        for(j = 0; j < 10; j++)
        {
            count[j] = 0;       // 每次分配前清空记录数
        }

        for(j = 0; j < n; j++)
        {
            k = (data[j] / radix) % 10;     // 统计每个桶中的记录数
            count[k]++;
        }

        for(j = 1; j < 10; j++)
        {
            count[j] = count[j-1] + count[j];       // 将temp中的位置依次分配给每个桶
        }

        for(j = n - 1; j >= 0; j--)
        {
            // 将所有桶中记录依次收集到temp中
            k = (data[j] / radix) % 10;
            temp[count[k] - 1] = data[j];
            count[k]--;
        }

        for(j = 0; j < n; j++)
        {
            // 将临时数组的内容复制到data中
            data[j] = temp[j];
        }

        radix = radix * 10;
    }
    
    delete []temp;
    delete []count;
}
